Graphs and arena allocation 图与竞技场分配

原文：
- https://github.com/nrc/r4cppp/blob/master/graphs/README.md
翻译者： Scott Huang
翻译日期： Sep 19, 2015 于厦门

（请注意，你可以通过下载该目录和cargo run运行本章例子)。

Rust严格的使用期lifetime和可变性mutability的要求导致构建图的方法有点笨拙。对象图在面向对象程序设计中非常常见。在本教程中，我将要详谈几个不同的实现方法。我的首选方法是使用竞技场arena分配，并稍微使用一些显式使用期(lieftime)的高级用法。我会在结束的时候讨论几个Rust潜在的特性，这些特性也许会使得尝试变容易一点。

一个图是一个节点的集合，其中一些节点有边连接。图是列表和树的泛化。每个节点可以有多个孩子和多个父母（我们通常谈论的是边接进入或伸出去一个节点，而不是父母/孩子）。图可以表示为邻接表或邻接矩阵。前者基本上是一个节点对象代表图的每个节点，其中每个节点对象保留其相邻节点的列表。邻接矩阵是一个布尔值矩阵，指示是否有边从行节点到列节点。我们将只讨论邻接表表示，邻接矩阵所具有的问题和邻接表有所不同，并且它们并非是Rust独有的问题。

有两个本质正交问题：如何处理图的使用期和如何处理图的可变性。

第一个问题本质上归结为用什么样的指针来指向图中的其他节点。由于图形类的数据结构是递归的（类型是递归的，即使数据不是递归的）我们也被迫使用某种指针，而不是一个完全基于值的结构。因为图可以循环的，但Rust的所有权不可循环，我们不能使用的Box<Node>作为我们的指针类型（正如我们可能做的树一样的数据结构或链表）。

没有图是真正不可变的。因为可能有循环，图不能在单语句中创建。因此，至少，图在初始化阶段必须是可变的。Rust存在一个普遍的本质规律，即所有的指针必须要么是独享的，要么是不可变的。图的边必须是可变的（至少在初始化期间），可以有一个以上的边连接到任何节点，因此，没有边保证是独一无二的。所以我们要做一点高级的处理绕过Rust的可变性限制。

一种解决方案是使用可变的裸指针（*mut Note）。这是最灵活的做法，也是最危险的。你必须在没有类型系统的任何帮助下手动管理所有的使用期。你可以用这种方式做出非常灵活和高效的数据结构，但你必须非常小心。这种尝试使用一种生猛的方法来处理使用期和可变性问题,本质上忽略了所有Rust的好处-你没有办法在这里得到编译器的帮助（这也不是特别便利，因为裸指针不自动解引用）。因为使用Rust裸指针处理一张图和使用C++处理一张图区别不大，所以，我不会在这里讨论。

您对使用期管理的可选项是引用计数（共享所有权，使用的是Rc<...>）或竞技场分配（所有节点都有被一个舞台所管理的相同的使用期；使用租借的引用&...）。前者更灵活（你可以拥有从图形外部的到个别点的任何生命周期的引用），后者是更好的其他方式。

至于管理可变性，您可以使用RefCell，即，利用Rust的动态、内部可变性设施，或者你可以自己管理可变性（在这种情况下，你必须使用UnsafeCell来和编译器沟通内部可变性）。前者更安全，后者更有效，都不是特别符合人体工程学。

请注意，如果你的图形可能有循环，那么如果你使用的是Rc，需要进一步的动作来打破循环而不泄漏内存。因为Rust没有循环Rc指针的集合，如果你的图有循环，引用计数将永远不会降到零，并且图形将不会释放。当你知道这个图应该被销毁，你可以在图中使用Weka弱指针解决这个问题或者手工打断循环。前者更可靠。我们也不再这里讨论，在我们的例子中，我们就是泄漏内存。使用租借引用和竞技场分配并没有这个问题，因此在这方面具有优势。

我会用一个非常简单的例子来比较不同的方法。我们会有一个Node对象代表图中的一个节点，它将有一些 String数据（代表一些更复杂的数据有效载荷）和Vec相邻节点（edges）。我们会有一个init函数来创建一个简单图节点，和一个traverse函数来遍历预先排序、深度优先的图。我们将用这个方法来打印每个节点的负载图。最后，我们将有一个Node::first的方法，它返回一个引用第一个相邻节点的self节点和功能foo，打印单个节点的负载。这些函数代替更为复杂的操作，涉及到图形的节点内部操作。

我将尽可能丰富信息而避免让你觉得无趣，我将覆盖2个组合的可能性：引用计数和RefCell，还有竞技台分配和UnsafeCell。我会把另外两个组合留作练习。

`Rc<RefCell<Node>>`

参考完整的例子.

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashSet;

struct Node {
    datum: &'static str,
    edges: Vec<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(datum: &'static str) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node {
            datum: datum,
            edges: Vec::new(),
        }))
    }

    fn traverse<F>(&self, f: &F, seen: &mut HashSet<&'static str>)
        where F: Fn(&'static str)
    {
        if seen.contains(&self.datum) {
            return;
        }
        f(self.datum);
        seen.insert(self.datum);
        for n in &self.edges {
            n.borrow().traverse(f, seen);
        }
    }

    fn first(&self) -> Rc<RefCell<Node>> {
        self.edges[0].clone()
    }
}

fn foo(node: &Node) {
    println!("foo: {}", node.datum);
}

fn init() -> Rc<RefCell<Node>> {
    let root = Node::new("A");

    let b = Node::new("B");
    let c = Node::new("C");
    let d = Node::new("D");
    let e = Node::new("E");
    let f = Node::new("F");

    {
        let mut mut_root = root.borrow_mut();
        mut_root.edges.push(b.clone());
        mut_root.edges.push(c.clone());
        mut_root.edges.push(d.clone());

        let mut mut_c = c.borrow_mut();
        mut_c.edges.push(e.clone());
        mut_c.edges.push(f.clone());
        mut_c.edges.push(root.clone());
    }

    root
}

pub fn main() {
    let g = init();
    let g = g.borrow();
    g.traverse(&|d| println!("{}", d), &mut HashSet::new());
    let f = g.first();
    foo(&*f.borrow());
}

'''
这是更安全的选择，因为没有不安全的代码。它也是最没有效率和最不人体工程学的选择。然而它是相当灵活的，图的节点可以很容易地在图外重复使用，因为他们是引用计数的。我会建议这种方法，如果你需要一个完全可变的图，或者你需要节点独立存在于图。

节点结构看起来像：

```rust
struct Node {
    datum: &'static str,
    edges: Vec<Rc<RefCell<Node>>>,
}

创建一个新的节点不是太糟糕：Rc::new(RefCell::new(Node { ... }))。在初始化期间添加一条边，你必须租借起始节点为可变的，并且克隆终端点到边Vec（这克隆指针，增加引用计数，而不是克隆实际的节点）。例如，

let mut mut_root = root.borrow_mut();
mut_root.edges.push(b.clone());

RefCell的动态确保我们不会在写入它的时候正在读取或者写入节点。

当你访问一个节点，你必须使用.borrow()来租借RefCell。我们的first第一个方法不得不返回一个引用计数的指针，而不是租借的引用，所以调用者的first也必须租借：

fn first(&self) -> Rc<RefCell<Node>> {
    self.edges[0].clone()
}

pub fn main() {
    let g = ...;
    let f = g.first();
    foo(&*f.borrow());
}

`&Node` and `UnsafeCell`

参考完整的例子.

use std::cell::UnsafeCell;
use std::collections::HashSet;
use arena::TypedArena;

struct Node<'a> {
    datum: &'static str,
    edges: UnsafeCell<Vec<&'a Node<'a>>>,
}

impl<'a> Node<'a> {
    fn new<'b>(datum: &'static str, arena: &'b TypedArena<Node<'b>>) -> &'b Node<'b> {
        arena.alloc(Node {
            datum: datum,
            edges: UnsafeCell::new(Vec::new()),
        })
    }

    fn traverse<F>(&self, f: &F, seen: &mut HashSet<&'static str>)
        where F: Fn(&'static str)
    {
        if seen.contains(&self.datum) {
            return;
        }
        f(self.datum);
        seen.insert(self.datum);
        unsafe {
            for n in &(*self.edges.get()) {
                n.traverse(f, seen);
            }
        }
    }

    fn first(&'a self) -> &'a Node<'a> {
        unsafe { (*self.edges.get())[0] }
    }
}

fn foo<'a>(node: &'a Node<'a>) {
    println!("foo: {}", node.datum);
}

fn init<'a>(arena: &'a TypedArena<Node<'a>>) -> &'a Node<'a> {
    let root = Node::new("A", arena);

    let b = Node::new("B", arena);
    let c = Node::new("C", arena);
    let d = Node::new("D", arena);
    let e = Node::new("E", arena);
    let f = Node::new("F", arena);

    unsafe {
        (*root.edges.get()).push(b);
        (*root.edges.get()).push(c);
        (*root.edges.get()).push(d);

        (*c.edges.get()).push(e);
        (*c.edges.get()).push(f);
        (*c.edges.get()).push(root);
    }

    root
}

pub fn main() {
    let arena = TypedArena::new();
    let g = init(&arena);
    g.traverse(&|d| println!("{}", d), &mut HashSet::new());
    foo(g.first());
}

在这种方法中，我们使用租借的引用作为边。这很好，符合人体工程学，并让我们用regular的Rust库，主要操作租借的引用（注意，关于Rust引用计数对象的一个很好的事是，他们和使用期系统配合得很好。我们可以创建一个租借的引用直接到Rc（并安全）参考的数据。在前面的例子，这RefCell阻止我们这样做，但Rc / UnsafeCell方法应该允许它）。

解构也被正确地处理过--唯一的约束就是所有的节点必须在同一时间被销毁。节点的销毁和分配都使用同一个竞技台。

另一方面，我们需要使用相当多的明确的使用期。不幸的是，我们无法从这里得到使用期省略的好处。在最后一节我将讨论一些可以使事情变好的语言的未来方向。

在构建过程中我们将改变我们的节点，也会改变多个引用。这不可能发生在Rust的安全代码，所以我们必须在一个不安全的unsafe块里初始化。既然我们的节点是可变的和多参考，我们必须使用一个UnsafeCell和Rust编译器打交道，它不能依赖它通常的不变量。

什么时候这种方法可行？图必须仅能在初始化时可改变。此外，我们要求图中的所有节点有相同的使用期（我们可以放松这些限制，允许后来添加节点，只要他们能在同一时间被销毁）。类似地，当节点可变时我们可以依赖于更复杂的不变量，但把事情简单化需要代价，因为程序员需要在这些方面自己负责安全。

竞技场分配是一个内存管理技术，其中一组对象有同样的使用期并可以在同一时间段释放。舞台是一个对象负责分配和释放内存。由于一次性地分配和释放大块内存（而不是一个个地分配），竞技场的分配是非常有效的。通常，所有的对象都是从一个连续的内存块的分配，当你遍历图时，提高了缓存一致性。

Rust中，舞台上的分配是由crate libarena支持,在整个编译器中使用。有2种类型竞技场 - 类型化和非类型化。前者是更有效和更容易使用，但只能分配单一类型对象。后者更灵活，可以分配任何对象。竞技场分配的对象都有相同的使用期，这是一个竞技场对象参数。类型系统确保竞技场分配的对象的引用不能比舞台本身活得更长。

我们的节点结构现在必须包括图的使用期，'a。我们包装我们Vec相邻节点在一个UnsafeCell，表明我们将改变它即使它应该是不可改变的：

struct Node<'a> {
    datum: &'static str,
    edges: UnsafeCell<Vec<&'a Node<'a>>>,
}

我们的新函数还必须使用这个使用期，必须作为一个竞技场分配的参数：

fn new<'a>(datum: &'static str, arena: &'a TypedArena<Node<'a>>) -> &'a Node<'a> {
    arena.alloc(Node {
        datum: datum,
        edges: UnsafeCell::new(Vec::new()),
    })
}

我们用竞技场来分配节点。图的使用期来自指向arena的引用的使用期，所以arena一定要从覆盖图的使用期的范围中传递进来。对于我们的例子，这意味着我们把它传递到init方法。（可以想象一个类型系统的扩展允许在其词汇范围以外创建值，但近期没有计划添加这样的东西）。当竞技场超出范围，整个图被销毁（Rust的类型系统确保我们不能在那一点上还保有对图形的引用）。

添加一个边看起来有点不同：

(*root.edges.get()).push(b);

我们本质上是在做明显的 root.edges.push(b)推一个节点（b）到边的列表。然而，由于edges包装在一个UnsafeCell，我们要在其上调用get()。这给了我们一个可变的裸指针到边(*mut Vec<&Node>)，这让我们改变edges。然而，它也需要我们手动解引用指针（裸指针不会自动解引用），因此需要(*...)。最后，对裸指针解引用是不安全的，整段都要被包裹在一个不安全的区域里。

traverse遍历的有趣部分是：

for n in &(*self.edges.get()) {
    n.traverse(f, seen);
}

我们遵循先前的模式来获取边的列表，这需要一个不安全块。在这种情况下，我们知道，这是安全的，因为我们必须是延后初始化，因此不会有改变。

再次，first方法遵循相同的模式得到的edges列表。又必须是在一个不安全的块。然而，在对比图使用Rc<RefCell<_>>，我们可以返回一个明确的租借引用到节点。那很方便。我们可以认为不安全的块是安全的因为我们没有改变，并且我们延后初始化。

fn first(&'a self) -> &'a Node<'a> {
    unsafe {
        (*self.edges.get())[0]
    }
}

Future language improvements for this approach

我相信竞技场分配和使用租借引用是一个重要的Rust模式。我们应该在语言层面做的更多，使这些模式更安全、更容易使用。我希望正在开发的allocators使得arena变得更加符合人体工程学。我看到了其它三个改进：

Safe initialisation 安全初始化

在面向对象的世界中有大量关于确保可变性仅发生在初始化期间的机制的研究。Rust在这方面如何工作的更精确是一个公开的研究课题，似乎我们需要表现一个指针是可变的，但不是唯一的，且必须限制在某个范围。超出该范围之外的任何现有的指针将成为正常的租借引用，即，不可变的或唯一的。

这样一个方案的优点是，在初始化期间我们有办法在初始化期间表达可变共同模式，然后不变。它也依赖于不变量的是，当单个个体对象是乘法拥有的，聚合（在这种情况下是一个图）是唯一拥有的。我们应该可以采取引用和UnsafeCell和方法，没有UnsafeCells和不安全块，使这种方法更符合人体工程学和更安全。

苏黎世联邦理工大学的Alex Summers和Julian Viereck正在进一步调查这个。

Generic modules 泛型模块

任何特定的图的图的使用期是恒定的。重复的使用期仅是样板代码。可以让其更便利的一个方法是允许图模块可以被使用期参数化，所以这就不需要被添加到每一个结构，impl，和函数。一个图的使用期仍然需要在模块外指定，但希望接口可以照顾大多数的使用（因为函数调用是这样的）。

请参考ref_graph_generic_mod.rs来看它大概是啥。（我们也应该能够使用安全初始化（上述建议的）来删除不安全的代码）。

又见RFC issue。

此功能将大大减少的引用和UnsafeCell方法的语法开销。

Lifetime elision 使用期缺省

我们现在允许程序员忽略一些使用期在函数签名来提高工效学。一个原因是图的&Note方法有点丑陋，因为它没有受益于任何的使用期省略规则。

Rust的一种常见的模式是数据结构用一个共同的使用期。这种数据结构的引用引起的类型如&'a Foo<'a>，例如&'a Node<'a> 在图的例子中。在这种情况下，有一个好的省略规则将起帮助。但我还不知道该如何工作。

用泛型模块的例子看，它看起来不像需要我们非常多地扩展使用期的省略规则（实际上我不知道 Node::new是否可以在没有给定使用期下工作，但即使不是的话，它似乎也是一个相当小的扩展便可以使它工作）。我们可能要增加一些新的规则允许省略泛型模块使用期，如果他们是唯一在范围（除'static外），但我不知道它如何与多个in-scope的使用期合作（见foo和init函数，例如）。

如果我们不加泛型模块，还可以添加一个省略规则，特别针对&'a Node<'a>目标，只是还不知道该怎样处理。

10.Graphs and arena allocation 图与竞技场分配

Graphs and arena allocation 图与竞技场分配

`Rc<RefCell<Node>>`

`&Node` and `UnsafeCell`

Future language improvements for this approach

Safe initialisation 安全初始化

Generic modules 泛型模块

Lifetime elision 使用期缺省

results matching ""

No results matching ""

Graphs and arena allocation 图与竞技场分配

Rc<RefCell<Node>>

&Node and UnsafeCell

Future language improvements for this approach

Safe initialisation 安全初始化

Generic modules 泛型模块

Lifetime elision 使用期缺省

results matching ""

No results matching ""

`Rc<RefCell<Node>>`

`&Node` and `UnsafeCell`